//给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n²] 范围内。除了 a 出现 两次，b 缺失 之外，每个整数都
// 恰好出现一次 。 
//
// 任务是找出重复的数字a 和缺失的数字 b 。 
//
// 返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。 
//
// 
//
// 示例 1： 
//
// 
//输入：grid = [[1,3],[2,2]]
//输出：[2,4]
//解释：数字 2 重复，数字 4 缺失，所以答案是 [2,4] 。
// 
//
// 示例 2： 
//
// 
//输入：grid = [[9,1,7],[8,9,2],[3,4,6]]
//输出：[9,5]
//解释：数字 9 重复，数字 5 缺失，所以答案是 [9,5] 。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= n == grid.length == grid[i].length <= 50 
// 1 <= grid[i][j] <= n * n 
// 对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的任何成员都不相等。 
// 对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的两个成员相等。 
// 除上述的两个之外，对于所有满足1 <= x <= n * n 的 x ，都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 
//grid[i][j] == x 。 
// 
//
// Related Topics 数组 哈希表 数学 矩阵 👍 23 👎 0


package LeetCode.editor.cn;

import java.util.stream.IntStream;

/**
 * @author ldltd
 * @date 2024-06-04 15:14:26
 * @description 2965.找出缺失和重复的数字
 */
public class FindMissingAndRepeatedValues{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindMissingAndRepeatedValues fun=new FindMissingAndRepeatedValues();
	 	 Solution solution = fun.new Solution();
			solution.findMissingAndRepeatedValues(new int[][]{{1,3},{2,2}});
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] findMissingAndRepeatedValues(int[][] grid) {
		int n = grid.length;
		int [] bo=new int[n*n+1];
		bo[0]=1;
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[0].length; j++) {
				bo[grid[i][j]]+=1;
			}
		}
		int[] result = new int[2];

		IntStream.range(0, bo.length)
				.filter(i -> bo[i] == 0 || bo[i] == 2)
				.forEach(i -> {
					if (bo[i] == 0) {
						result[1] = i; // Missing value
					} else if (bo[i] == 2) {
						result[0] = i; // Repeated value
					}
				});

		return result;
	}
	//位运算，时间on2,空间O1
	public int[] findMissingAndRepeatedValues1(int[][] grid) {
		int n = grid.length;
		int xorAll = 0;
		//先异或1~n^2，则最后会有数出现1和3 次，其余都是两次
		for (int[] row : grid) {
			for (int x : row) {
				xorAll ^= x;
			}
		}
		// n的奇偶性会影响

		/*
		*0^1=1
		* 2^3=1
		* 4^5=1,
		* 当x是偶数时，只有最低位不同，则结果为1
		* 把0~n分为两两一组
		* n=4k+3时，3,7,11,可以分为2（k+1）组（包括0)，结果为0
		* n=4K+1时，1,5，9，可以分成2k+1组，结果为1
		* n=4k+2时，2,6,10，可以变成4k+1+1，即n+1
		* n=4k+4市，4,8,12，变成4k+3+1,即n
		* 所以n是偶数对应n^2，否则等于1 ，n^2模4要么是1要么是0 */
		xorAll ^= n % 2 > 0 ? 1 : n * n;
		//返回整数类型的给定参数[value]的2的补码表示法中最右边一位之后的0位数
		int shift = Integer.numberOfTrailingZeros(xorAll);

		int[] ans = new int[2];
		for (int x = 1; x <= n * n; x++) {
			ans[x >> shift & 1] ^= x;
		}
		for (int[] row : grid) {
			for (int x : row) {
				ans[x >> shift & 1] ^= x;
			}
		}

		for (int[] row : grid) {
			for (int x : row) {
				if (x == ans[0]) {
					return ans;
				}
			}
		}
		return new int[]{ans[1], ans[0]};
	}
	/*数学，计算1~n^的和减去数组得到a-b
	再计算1~n^的平方和减去数组的平方和，得到a^2-b^2
	a^2-b^2=(a+b)(a-b)
	解方程
	* */
	public int[] findMissingAndRepeatedValues2(int[][] grid) {
		int n = grid.length;
		int m = n * n;
		int d1 = -m * (m + 1) / 2;
		//m=n^2,1到m的和为m(m+1)/2，平方和为m(m+1)(2m+1）/6
		long d2 = (long) -m * (m + 1) * (m * 2 + 1) / 6;
		for (int[] row : grid) {
			for (int x : row) {
				d1 += x;
				d2 += x * x;
			}
		}
		//得到a+b
		int d = (int) (d2 / d1);
		return new int[]{(d + d1) / 2, (d - d1) / 2};
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
